package com.mlamp.排序;

import java.util.Arrays;

public class 快速排序 {


    public static int[] qsort(int[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end >= array.length) return array;
        int smallIndex = partition1(array, start, end);
        if (smallIndex > start) qsort(array, start, smallIndex - 1);
        if (smallIndex < end) qsort(array, smallIndex + 1, end);
        return array;
    }


    public static void qsort2(int[] array, int start, int end) {
        if (array == null || array.length < 1 || start < 0 || end > array.length - 1) return;
        int sidx = partition222(array, start, end);
        if (sidx > start) {
            qsort2(array, start, sidx - 1);
        }
        if (sidx < end) {
            qsort2(array, sidx + 1, end);
        }
    }

    private static int partition23(int[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        int temp = array[pivot];
        array[pivot] = array[end];
        array[end] = temp;
        for (int i = start; i <= end; i++) {
            if (array[i] <= array[end]) {
                smallIndex++;
                if (smallIndex < i) {
                    int tmp = array[smallIndex];
                    array[smallIndex] = array[i];
                    array[i] = tmp;
                }
            }
        }
        return smallIndex;
    }

    private static int partition222(int[] array, int start, int end) {
        int pivotIndex = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        //swap the pivot and end
        int tmp = array[pivotIndex];
        array[pivotIndex] = array[end];
        array[end] = tmp;
        for (int i = start; i <= end; i++) {
            if (array[i] <= array[end]) {
                smallIndex++;
                if (smallIndex < i) {
                    int temp = array[smallIndex];
                    array[smallIndex] = array[i];
                    array[i] = temp;
                }
            }
        }
        return smallIndex;
    }


    private static int partition1(int[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        swap(array, pivot, end);
        for (int index = start; index <= end; index++) {
            if (array[index] < array[end]) {
                smallIndex++;
                if (index > smallIndex) {
                    swap(array, index, smallIndex);
                }
            }
        }
        return smallIndex;
    }

    private static void qsort23(int[] array, int start, int end) {
        if (array == null || array.length < 1 || start < 0 || end > array.length) return;
        int i = partition23(array, start, end);
        if (i > start) qsort23(array, start, i - 1);
        if (i < end) qsort23(array, i + 1, end);
    }


    private static int partition22(int[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        int temp = array[pivot];
        array[pivot] = array[end];
        array[end] = temp;
        for (int i = start; i <= end; i++) {
            if (array[i] <= array[end]) {
                smallIndex++;
                if (i > smallIndex) {
                    int tmp = array[smallIndex];
                    array[smallIndex] = array[i];
                    array[i] = tmp;
                }
            }
        }
        return smallIndex;
    }

    public static void main(String[] args) {
        int[] input = new int[]{2, 3, 4, 2, 12, 34, 32};
        //qsort23(input, 0, input.length - 1);
        qsort2(input, 0, input.length - 1);
        System.out.println(Arrays.toString(input));

    }

    public static void qsort1(int[] array, int start, int end) {
        if (array == null || array.length == 0 || start < 0 || end > array.length - 1) return;
        int partitionIdx = partition2(array, start, end);
        if (partitionIdx > start) qsort1(array, start, partitionIdx - 1);
        if (partitionIdx < end) qsort1(array, partitionIdx + 1, end);
    }


    private static int partition2(int[] array, int start, int end) {
        int pivotIdx = (int) (start + Math.random() * (end - start + 1));
        //swap the end element with pivot
        int temp = array[end];
        array[end] = array[pivotIdx];
        array[pivotIdx] = temp;
        int smallIndex = start - 1;
        for (int i = start; i <= end; i++) {
            if (array[i] <= array[end]) {
                smallIndex++;
                if (i > smallIndex) {
                    //swap the element located at i and smallIndex
                    int tmp = array[i];
                    array[i] = array[smallIndex];
                    array[smallIndex] = tmp;
                }
            }
        }
        return smallIndex;
    }


    public static int[] quicksort(int[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end >= array.length) return null;
        int smallIndex = partition(array, start, end);
        if (smallIndex > start) {
            quicksort(array, start, smallIndex - 1);
        }
        if (smallIndex < end) {
            quicksort(array, smallIndex + 1, end);
        }
        return array;
    }

    public static int partition(int array[], int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        swap(array, pivot, end);
        for (int index = start; index <= end; index++) {
            if (array[index] < array[end]) {
                smallIndex++;
                if (index > smallIndex) {
                    swap(array, index, smallIndex);
                }
            }
        }
        return smallIndex;
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

